package leetcode.p448;

import java.util.ArrayList;
import java.util.List;

/***
 * 1到n范围内没有出现的数字
 * 思路：遍历nums，每个元素减一作为index 去看nums[index]上的值是大于零吗？如果大于零，就取反。最后看哪个位置是正数。就是缺少index+1  那个数字。
 */
public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        for (int i=0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if(nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        for (int j = 0; j < nums.length; j++) {
            if(nums[j] > 0){
                result.add(j+1);
            }
        }
        return result;
    }
}
